//#include<bits/stdc++.h>
//using namespace std;
//unordered_map<string, string>mp;
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    vector<string>v1(1000);
//    vector<string>v2(1000);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v1[i] >> v2[i];
//        mp[v1[i]] = v2[i];
//    }
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n; j++)
//        {
//            if (i == j)
//                continue;
//            string ss;
//            ss += v1[i];
//            ss += v1[j];
//            string sss;
//            sss += v2[i];
//            sss += v2[j];
//            mp[ss] = sss;
//        }
//    for (int i = 0; i < m; i++)
//    {
//        string s;
//        cin >> s;
//        if (mp.count(s) == 0)
//            cout << 'D' << endl;
//        else
//            cout << mp[s] << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//unordered_map<string, int>mp;
//unordered_map<int, string>mp;
//int pos = 1;
//int idx;
//int e[1010], ne[1010], h[1010];
//void add(int a, int b)
//{
//    e[idx] = b;
//    ne[idx] = h[a];
//    h[a] = idx++;
//}
//bool is[1010] = { 0 };
//int dp[1010] = { 0 };
//int dij(int point)
//{
//    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
//    pq.push({ 0,point });
//    while (pq.size())
//    {
//        auto at = pq.top();
//        pq.pop();
//        int dis = at.first, pp = at.second;
//        for (int i = h[pp]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (is[j] == 0) {
//                pq.push(j)
//            }
//        }
//    }
//}
//int main()
//{
//    int n;
//    cin >> n;
//    memset(h, -1, sizeof h);
//    vector<string>v(n * 2 + 1);
//    for (int i = 0; i < n; i++)
//    {
//        string s1, s2;
//        int a1, a2;
//        cin >> s1 >> a1 >> s2 >> a2;
//        s1 += '0' + a1;
//        s2 += '0' + a2;
//        if (mp.count(s1))
//            mp[s1] = pos++;
//        if (mp.count(s2))
//            mp[s2] = pos++;
//        add(mp[s1], mp[s2]);
//    }
//    memset(dp, 0x3f, sizeof dp);
//    int Min = 0x3f3f3f3f;
//    for (auto at : mp)
//       Min=dij(at.second);
//        return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//unordered_map<string, int>mp;
//unordered_map<int, string>mp2;
//int pos = 1;
//int idx;
//int e[1010], ne[1010], h[1010];
//void add(int a, int b)
//{
//    e[idx] = b;
//    ne[idx] = h[a];
//    h[a] = idx++;
//}
//bool is[1010] = { 0 };
////int dp[1010] = { 0 };
//vector<string>ans;
//bool dij(int point)
//{
//    queue<int>pq;
//    pq.push(point );
//    while (pq.size())
//    {
//        auto at = pq.front();
//        pq.pop();
//        ans.push_back(mp2[at]);
//        for (int i = h[at]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (is[j] == 0) {
//                pq.push(j);
//                is[j] = 1;
//                if (mp2[j] == mp2[point])
//                {
//                    ans.push_back(mp2[j]);
//                    return 1;
//                }
//            }
//        }
//    }
//    return 0;
//}
//int main()
//{
//    int n;
//    cin >> n;
//    memset(h, -1, sizeof h);
//    vector<string>v(n * 2 + 1);
//    for (int i = 0; i < n; i++)
//    {
//        string s1, s2;
//        int a1, a2;
//        cin >> s1 >> a1 >> s2 >> a2;
//        s1 += '0' + a1;
//        s2 += '0' + a2;
//        if (mp.count(s1)==0)
//        {
//            mp[s1] = pos++;
//            mp2[pos - 1] = s1;
//        }
//        if (mp.count(s2)==0)
//        {
//            mp[s2] = pos++;
//            mp2[pos - 1] = s2;
//        }
//        add(mp[s1], mp[s2]);
//    }
//    //memset(dp, 0x3f, sizeof dp);
//    int Min = 0x3f3f3f3f;
//    vector<string>ANS;
//    for (auto at : mp)
//    {
//        memset(is, 0, sizeof is);
//        if (dij(at.second))
//        {
//            if (ans.size() < Min)
//                ANS = ans;
//            Min = ans.size();
//        }
//    }
//    for (auto s : ANS)
//    {
//        for (int i = 0; i < s.size() - 2; i++)
//            cout << s[i];
//        cout << ' ';
//        cout << s[s.size() - 1]<<' ';
//    }
//    cout << '=';
//    cout << ' ';
//    string first = ANS[0];
//    for (int i = 0; i < first.size() - 2; i++)
//        cout << first[i] ;
//    cout << ' ';
//    cout << first[first.size() - 1] << ' ';
//    cout << ' ';
//    for (int i = 0; i < first.size() - 2; i++)
//        cout << first[i];
//    cout << ' ';
//    cout << (first[first.size() - 1]=='0'?'1':'0') << ' ';
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//unordered_map<string, string>mp1;
//unordered_map<string, string>mp2;
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    vector<string>v1(1000);
//    vector<string>v2(1000);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v1[i] >> v2[i];
//        if (mp1.count(v1[i]) == 0)
//            mp1[v1[i]] = v2[i];
//        else
//            mp1[v1[i]] = "D";
//    }
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n; j++)
//        {
//            //  if(i==j)
//                //  continue;
//            string ss;
//            ss += v1[i];
//            ss += v1[j];
//            string sss;
//            sss += v2[i];
//            sss += v2[j];
//            if (mp2.count(ss) == 0)
//                mp2[ss] = sss;
//            else
//                mp2[ss] = "D";
//        }
//    for (int i = 0; i < m; i++)
//    {
//        string s;
//        cin >> s;
//        if (mp1.count(s))
//            cout << mp1[s];
//        else if (mp2.count(s) == 0)
//            cout << 'D';
//        else
//            cout << mp2[s];
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//    int n;
//    cin >> n;
//    vector<int>v(n);
//    for (int i = 0; i < n; i++)cin >> v[i];
//    int begin = 0, end = 0;
//    int flag = 0;
//    int x;
//    for (int i = 0; i < n; i++)
//    {
//        x = v[i];
//        if (flag == 0)
//        {
//            begin = x + 15;
//            end = begin + 29;
//            flag++;
//        }
//        else if (flag == 1 && x < begin)
//            ;
//        else if (flag == 1 && x >= begin && x <= end)
//        {
//            end += 15; flag++;
//        }
//        else if (flag && end <= x) {
//            cout << begin << ' ' << end << endl;
//            begin = x + 15, end = begin + 29;
//            flag = 1;
//        }
//    }
//        if (flag && end > x)
//            cout << begin << ' ' << end << endl;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//struct at {
//    int x, y;
//} guai[4];
//int d1, d2;
//int T_x, T_y;
//typedef pair<int, int> PII;
//bool dead(int x, int y) {
//    if (x == guai[2].x || x == guai[3].x)
//        return 0;
//    if (y == guai[0].x || y == guai[0].x)
//        return 0;
//    return 1;
//}
//class great {
//public:
//    bool operator()(PII& p1, PII& p2)
//    {
//        return p1.first == p2.first ? p1.second > p2.second:p1.first > p2.first;
//    }
//};
//unordered_map<PII, bool>mp1;
//unordered_map<PII, bool>mp2;
//unordered_map<PII,PII>mp3;
//int main()
//{
//    cin >> guai[0].x >> guai[1].x >> guai[2].x >> guai[3].x;
//    cin >> guai[0].y >> guai[1].y >> guai[2].y >> guai[3].y;
//    for (int i = 0; i < 4; i++)
//        guai[i].x += guai[i].y;
//    cin >> T_x >> T_y >> d1 >> d2;
//    priority_queue<PII, vector<PII>, great>pq;
//    priority_queue<PII, vector<PII>, great>pq1;
//    for (int i = 0; i < 5; i++)
//        for (int j = 0; j < 5; j++)
//            if (abs(i - T_x) + abs(j - T_y) == d2 && mp1.count({ i,j }) == 0)
//            {
//                pq.push({ i,j });
//                mp1[make_pair(i, j)] = 1;
//            }
//    for (int i = 0; i < 4; i++)
//        guai[i].x -= guai[i].y;
//    while (pq.size())
//    {
//        int k = pq.top().first;
//        int jj = pq.top().second;
//        pq.pop();
//        for (int i = 0; i < 5; i++)
//            for (int j = 0; j < 5; j++)
//            {
//                if (abs(i - k) + abs(jj - j) == d1 && mp2.count({ i,j }))
//                    pq1.push({ i,j });
//                mp2[make_pair(i, j)] = 1;
//                mp3[make_pair(i, j)] = make_pair(k,jj);
//            }
//    }
//    while (pq.size())
//    {
//        PII pp = pq.top();
//        pq.pop();
//        cout << pp.first << ' ' << pp.second<<' ';
//        pp = mp3[pp];
//        cout << pp.first << ' ' << pp.second;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1010;
//const int M = 5050;
//int e[M], ne[M], h[M];
//int dis[N][N];
//int n, m, s, t;
//int idx;
//int hot[N];
//int pre[M];
//bool id[N];
//void add(int a, int b) {
//    e[idx] = b;
//    ne[idx] = h[a];
//    h[a] = idx++;
//}
//int dp[N];
//struct K
//{
//    int pos, money;
//    bool operator<(K k)const {
//        return money > k.money;
//    }
//};
//void dij()
//{
//    priority_queue<K>pq;
//    K kk = { s,0 };
//    pq.push(kk);
//    dp[s] = 0;
//    while (pq.size())
//    {
//        struct K at = pq.top();
//        pq.pop();
//        int pos = at.pos, money = at.money;
//        for (int i = h[pos]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dp[j] > dp[pos] + dis[pos][j])
//            {
//                dp[j] = dp[pos] + dis[pos][j];
//                K k1 = { j,dp[j] };
//                pq.push(k1);
//                pre[j] = pos;
//            }
//        }
//    }
//    if (dp[t] == 0x3f3f3f3f)
//        cout << "Impossible";
//    else
//    {
//        int hhot = 0;
//        while (pre[t] != -1)
//        {
//            hhot = max(hhot, hot[t]);
//            t = pre[t];
//        }
//        cout << dp[t] << ' ' << hhot;
//    }
//}
//
//int main()
//{
//    memset(h, -1, sizeof h);
//    memset(dp, 0x3f, sizeof dp);
//    memset(dis, 0x3f, sizeof dis);
//    memset(pre, -1, sizeof pre);
//    cin >> n >> m >> s >> t;
//    for (int i = 1; i <= n; i++)
//        dis[i][i] = 0;
//    for (int i = 1; i <= n; i++)cin >> hot[i];
//    for (int i = 0; i < m; i++)
//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//        add(x, y);
//        add(y, x);
//        dis[x][y] = z;
//        dis[y][x] = z;
//    }
//    dij();
//}
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//	int T;
//	cin >> T;
//	while (T--)
//	{
//		int a, b,c;
//		cin >> a >> b>>c;
//		vector<int>v(b + 1);
//		for (int i = 1; i <= b; i++)
//			cin >> v[i];
//		sort(v.begin(), v.end());
//		int sum = 0;
//		for (int i = 2; i <= b; i++)
//			sum += (v[i] - v[i - 1] == 2);
//		sum += (v[1] + a - v[b] == 2);
//		cout << sum + b - 2 << endl;
//	}
//	return 0;
//}